/* 顺序表C语言实现 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

constexpr int TRUE = 1;
constexpr int FALSE = 0;
constexpr int OK = 1;
constexpr int ERROR = 0;
constexpr int INFEASIBLE = -1;
constexpr int OVERFLOW = -2;

typedef int Status;							// 函数的返回类型
typedef int ElemType;						// 数据元素的类型
typedef int (*Compare)(ElemType, ElemType); // 比较函数的指针

constexpr int MaxLen = 100; 

/* 静态数组实现 */
typedef struct {
	ElemType List[MaxLen];
	int ListLen;
} SqList_Static;

// 初始化
static void SqList_StaticInit(SqList_Static *L) {
	for (int i = 0;i < MaxLen;i++) {
		L->List[i] = 0;
	}
	L->ListLen = 0;
	return;
}

// 将线性表重置为空表
static Status SqList_StaticClear(SqList_Static *L) {
	for (int i = 0; i < L->ListLen; i++) {
		L->List[i] = 0;
	}
	L->ListLen = 0;
	return OK;
}

// 判断线性表是否为空表
static Status SqList_StaticIsEmpty(SqList_Static* L) {
	if (L->ListLen == 0) return TRUE;
	else return FALSE;
}

// 返回元素个数
static int SqList_StaticLength(SqList_Static* L) {
	return L->ListLen;
}

// 获取线性表中第i个元素的值，并用指针e返回
static Status SqList_StaticGetElem(SqList_Static* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen) exit(OVERFLOW);
	else {
		e = &(L->List[i]);
		return OK;
	}
}

// 寻找元素位序 (顺序查找L中符合"Compare类型"函数的第一个元素)
static int SqList_StaticLocateElem(SqList_Static* L, ElemType e, Compare cmp) {
	for (int i = 0; i < L->ListLen; i++) {
		if (cmp(L->List[i], e)) {
			return i + 1; // 从下标到位序需要加1
		}
	}
	return ERROR;
}

// 返回指定元素的前驱，如果元素存在并用pre_e指针返回，否则返回错误代码
static Status SqList_StaticPriorElem(SqList_Static* L, ElemType e, ElemType* pre_e) {
	for (int i = 0; i < L->ListLen; i++) {
		if (L->List[i] == e) {
			pre_e = &(L->List[i - 1]);
			return OK;
		}
	}
	return ERROR;
}

// 返回指定元素的后继，如果元素存在并用next_e指针返回，否则返回错误代码
static Status SqList_StaticNextElem(SqList_Static* L, ElemType e, ElemType* next_e) {
	for (int i = 0; i < L->ListLen - 1; i++) {
		if (L->List[i] == e) {
			next_e = &(L->List[i + 1]);
			return OK;
		}
	}
	return ERROR;
}

// 在L中的指定位序i插入元素e，并返回状态码(指针传递)
static Status SqList_StaticInsert(SqList_Static* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen + 1) exit(INFEASIBLE);
	if (L->ListLen == MaxLen) exit(OVERFLOW);
	for (int j = L->ListLen - 1; j >= i - 1; j--) {
		L->List[j + 1] = L->List[j];
	}
	L->List[i - 1] = *e;
	return OK;
}

// 在L中的指定位序i插入元素e，并返回状态码(传值传递)
static Status SqList_StaticInsert(SqList_Static* L, int i, ElemType e) {
	if (i <= 0 || i > L->ListLen + 1) exit(INFEASIBLE);
	if (L->ListLen == MaxLen) exit(OVERFLOW);
	for (int j = L->ListLen - 1; j >= i - 1; j--) {
		L->List[j + 1] = L->List[j];
	}
	L->List[i - 1] = e;
	L->ListLen++;
	return OK;
}

// 在L中的删除第i个元素，并用指针e返回被删除元素的地址
static Status SqList_StaticDelete(SqList_Static* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen) exit(INFEASIBLE);
	for (int j = i - 1; j < L->ListLen - 1; j++) {
		L->List[j] = L->List[j + 1];
	}
	L->ListLen--;
	return OK;
}

// 打印线性表(仅限int类型)
static void SqList_StaticPrint(SqList_Static* L) {
	printf("<SqList_Static> [ ");
	for (int i = 0; i < L->ListLen; i++) {
		printf("%d", L->List[i]);
		if (i != L->ListLen - 1) printf(", ");
		else printf(" ");
	}
	printf("]\tLength = %d\n\n", L->ListLen);
	return;
}

// 交互输入数据元素 特殊输入-9999结束 (仅限int类型) 
static Status SqList_StaticInput(SqList_Static* L) {
	if (L->ListLen != 0) exit(INFEASIBLE);
	ElemType tmp = 0;
	scanf("%d", &tmp);
	while(tmp != -9999 && L->ListLen <= MaxLen) {
		L->List[L->ListLen++] = tmp;
		scanf("%d", &tmp);
	}
	return OK;
}

// 随机数创建顺序表 (仅限int类型)
static Status SqList_StaticRandom(SqList_Static* L, int Length, int LD, int LU) {
	if (L->ListLen != 0 || MaxLen < Length) exit(INFEASIBLE);
	srand((unsigned int)time(NULL));
	for (int i=0;i < Length;i++) {
		L->List[i] = LD + rand() % (LU - LD);
	}
	L->ListLen = Length;
	return OK;
}

// 有序合并两个有序线性表LA和LB 并储存于新表LC中
static Status SqList_StaticMerge(SqList_Static* La, SqList_Static* Lb, SqList_Static* Lc) {
	int i = 0, j = 0;
	while ( i < La->ListLen && j < Lb->ListLen) {
		if (La->List[i] <= Lb->List[j]) {
			Lc->List[Lc->ListLen++] = La->List[i];
			if (La->List[i] == Lb->List[j]) j++;
			i++;
		}
		else {
			Lc->List[Lc->ListLen++] = Lb->List[j];
			if (La->List[i] == Lb->List[j]) i++;
			j++;
		}
	}
	while (i < La->ListLen) Lc->List[Lc->ListLen++] = La->List[i++];
	while (j < Lb->ListLen) Lc->List[Lc->ListLen++] = Lb->List[j++];
	return OK;
}

/* 动态数组实现 (动态内存分配) */
typedef struct {
	ElemType *List;
	int ListLen;
	int MemeLen;
} SqList_Dynamic;

// 初始化
static Status SqList_DynamicInit(SqList_Dynamic* L) {
	L->MemeLen = 100;
	L->List = (ElemType*)malloc(L->MemeLen * sizeof(ElemType));
	if (L != NULL) L->ListLen = 0;
	else return ERROR;
	return OK;
}

// 销毁回收
static Status SqList_DynamicDestroy(SqList_Dynamic* L) {
	if (L->List != NULL) {
		free(L->List);
		L->List = NULL;
		return OK;	
	}
	else {
		return ERROR;
	}
}

// 将线性表重置为空表
static Status SqList_DynamicClear(SqList_Dynamic* L) {
	for (int i = 0; i < L->ListLen; i++) {
		L->List[i] = 0;
	}
	L->ListLen = 0;
	return OK;
}

// 判断线性表是否为空表
static Status SqList_DynamicIsEmpty(SqList_Dynamic* L) {
	if (L->ListLen == 0) return TRUE;
	else return FALSE;
}

// 返回元素个数
static int SqList_DynamicLength(SqList_Dynamic* L) {
	return L->ListLen;
}

// 获取线性表中第i个元素的值，并用指针e返回
static Status SqList_DynamicGetElem(SqList_Dynamic* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen) exit(OVERFLOW);
	else {
		e = &(L->List[i]);
		return OK;
	}
}

// 寻找元素位序 (顺序查找L中符合"Compare类型"函数的第一个元素)
static int SqList_DynamicLocateElem(SqList_Dynamic* L, ElemType e, Compare cmp) {
	for (int i = 0; i < L->ListLen; i++) {
		if (cmp(L->List[i], e)) {
			return i + 1; // 从下标到位序需要加1
		}
	}
	return ERROR;
}

// 返回指定元素的前驱，如果元素存在并用pre_e指针返回，否则返回错误代码
static Status SqList_DynamicPriorElem(SqList_Dynamic* L, ElemType e, ElemType* pre_e) {
	for (int i = 0; i < L->ListLen; i++) {
		if (L->List[i] == e) {
			pre_e = &(L->List[i - 1]);
			return OK;
		}
	}
	return ERROR;
}

// 返回指定元素的后继，如果元素存在并用next_e指针返回，否则返回错误代码
static Status SqList_DynamicNextElem(SqList_Dynamic* L, ElemType e, ElemType* next_e) {
	for (int i = 0; i < L->ListLen - 1; i++) {
		if (L->List[i] == e) {
			next_e = &(L->List[i + 1]);
			return OK;
		}
	}
	return ERROR;
}

// 在L中的指定位序i插入元素e，并返回状态码(指针传递)
static Status SqList_DynamicInsert(SqList_Dynamic* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen + 1) exit(INFEASIBLE);
	if (L->ListLen == L->MemeLen) {// 动态数组不受内存限制
		L->MemeLen++;
		ElemType* test = (ElemType*)realloc(L->List, L->MemeLen * sizeof(ElemType));
		if (test == NULL) exit(OVERFLOW);
	}
	for (int j = L->ListLen - 1; j >= i - 1; j--) {
		L->List[j + 1] = L->List[j];
	}
	L->List[i - 1] = *e;
	L->ListLen++;
	return OK;
}

// 在L中的指定位序i插入元素e，并返回状态码(传值传递)
static Status SqList_DynamicInsert(SqList_Dynamic* L, int i, ElemType e) {
	if (i <= 0 || i > L->ListLen + 1) exit(INFEASIBLE);
	if (L->ListLen == L->MemeLen) {// 动态数组不受内存限制
		L->MemeLen++;
		ElemType* test = (ElemType*)realloc(L->List, L->MemeLen * sizeof(ElemType));
		if (test == NULL) exit(OVERFLOW);
	}
	for (int j = L->ListLen - 1; j >= i - 1; j--) {
		L->List[j + 1] = L->List[j];
	}
	L->List[i - 1] = e;
	L->ListLen++;
	return OK;
}

// 在L中的删除第i个元素，并用指针e返回被删除元素的地址
static Status SqList_DynamicDelete(SqList_Dynamic* L, int i, ElemType* e) {
	if (i <= 0 || i > L->ListLen) exit(INFEASIBLE);
	for (int j = i - 1; j < L->ListLen - 1; j++) {
		L->List[j] = L->List[j + 1];
	}
	L->ListLen--;
	return OK;
}

// 打印线性表(仅限int类型)
static void SqList_DynamicPrint(SqList_Dynamic* L) {
	printf("<SqList_Dynamic> [ ");
	for (int i = 0; i < L->ListLen; i++) {
		printf("%d", L->List[i]);
		if (i != L->ListLen - 1) printf(", ");
		else printf(" ");
	}
	printf("]\tLength = %d\n\n", L->ListLen);
	return;
}

// 交互输入数据元素 特殊输入-9999结束 (仅限int类型) 
static Status SqList_DynamicInput(SqList_Dynamic *L) {
	if (L->ListLen != 0) exit(INFEASIBLE);
	ElemType tmp = 0;
	scanf("%d", &tmp);
	while(tmp != -9999) {
		if (L->ListLen > L->MemeLen) {
			void *tmp = (void*)realloc(L->List, sizeof(int) * (++L->MemeLen));
			if (tmp == NULL)  exit(INFEASIBLE);
		}
		L->List[L->ListLen++] = tmp;
		scanf("%d", &tmp);
	}
	return OK;
}

// 随机数创建顺序表 (仅限int类型)
static Status SqList_DynamicRandom(SqList_Dynamic *L, int Length, int LD, int LU) {
	if (L->ListLen != 0) exit(INFEASIBLE);
	if (L->MemeLen < Length) {
		void *tmp = (void*)realloc(L->List, sizeof(int) * Length);
		if (tmp == NULL)  exit(INFEASIBLE);
		L->MemeLen = Length;
	}
	srand((unsigned int)time(NULL) + 123);
	for (int i=0;i < Length;i++) {
		L->List[i] = LD + rand() % (LU - LD);
	}
	L->ListLen = Length;
	return OK;
}

// 有序合并两个有序线性表LA和LB 并储存于新表LC中
static Status SqList_DynamicMerge(SqList_Dynamic* La, SqList_Dynamic* Lb, SqList_Dynamic* Lc) {
	int i = 0, j = 0;
	while (i < La->ListLen && j < Lb->ListLen) {
		if (Lc->ListLen >= Lc->MemeLen) {printf("111\n\n");
			void* tmp = realloc(Lc->List, sizeof(ElemType) * (++Lc->MemeLen));
			if (tmp == NULL) return ERROR;
		}
		if (La->List[i] <= Lb->List[j]) {
			Lc->List[Lc->ListLen++] = La->List[i];
			if (La->List[i] == Lb->List[j]) j++;
			i++;
		}
		else {
			Lc->List[Lc->ListLen++] = Lb->List[j];
			if (La->List[i] == Lb->List[j]) i++;
			j++;
		}
	}
	while (i < La->ListLen) Lc->List[Lc->ListLen++] = La->List[i++];
	while (j < Lb->ListLen) Lc->List[Lc->ListLen++] = Lb->List[j++];
	return OK;
}

int main(void) {
    
	return 0;
}